package _interview100;

import java.util.Arrays;

/**
 * 53. 最大子数组和
 */
public class No53 {
    /*
      一、动态规划
     */
    private int[] nums;
    private int[] cache;

    /**
     * 1. 递归
     */
    public int maxSubArray11(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        cache = new int[n];
        Arrays.fill(cache, Integer.MIN_VALUE);

        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, dfs(i));
        }
        return ans;
    }

    private int dfs(int i) {
        if (i < 0) return Integer.MIN_VALUE / 2;
        else if (cache[i] != Integer.MIN_VALUE) return cache[i];
        else return cache[i] = Math.max(dfs(i - 1) + nums[i], nums[i]);
    }

    /**
     * 2. 迭代
     */
    public int maxSubArray12(int[] nums) {
        int n = nums.length;

        int ans = Integer.MIN_VALUE;

        int[] f = new int[n + 1];
        f[0] = Integer.MIN_VALUE / 2;
        for (int i = 0; i < n; i++) {
            f[i + 1] = Math.max(f[i] + nums[i], nums[i]);
            ans = Math.max(ans, f[i + 1]);
        }

        return ans;
    }

    /**
     * 4. 空间优化
     */
    public int maxSubArray14(int[] nums) {
        int ans = Integer.MIN_VALUE;

        int f1 = Integer.MIN_VALUE / 2;
        for (int num : nums) {
            f1 = Math.max(f1 + num, num);
            ans = Math.max(ans, f1);
        }

        return ans;
    }

    /*
      二、贪心
     */
    public int maxSubArray2(int[] nums) {
        int ans = Integer.MIN_VALUE;

        int curSum = 0;
        for (int num : nums) {
            curSum += num;
            if (curSum > ans) ans = curSum;
            if (curSum < 0) curSum = 0;
        }

        return ans;
    }

    /*
      三、分治
     */
    public int maxSubArray3(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        return maxSubArraySum(nums, 0, len - 1);
    }

    private int maxSubArraySum(int[] nums, int left, int right) {
        if (left == right) return nums[left];

        int mid = left + (right - left) / 2;

        return Math.max(maxCrossingSum(nums, left, mid, right),
                Math.max(maxSubArraySum(nums, left, mid),
                        maxSubArraySum(nums, mid + 1, right)));
    }

    private int maxCrossingSum(int[] nums, int left, int mid, int right) {
        // 一定会包含 nums[mid] 这个元素
        int curSum = 0;
        int leftSum = Integer.MIN_VALUE;
        // 左半边包含 nums[mid] 元素，最多可以到什么地方
        // 走到最边界，看看最值是什么
        // 计算以 mid 结尾的最大的子数组的和
        for (int i = mid; i >= left; i--) {
            curSum += nums[i];
            if (curSum > leftSum) leftSum = curSum;
        }

        curSum = 0;
        int rightSum = Integer.MIN_VALUE;
        // 右半边不包含 nums[mid] 元素，最多可以到什么地方
        // 计算以 mid+1 开始的最大的子数组的和
        for (int i = mid + 1; i <= right; i++) {
            curSum += nums[i];
            if (curSum > rightSum) rightSum = curSum;
        }
        return leftSum + rightSum;
    }
}
